1. Field of the Invention
The present invention relates to a method for performing packet flooding for transferring a broadcast packet from a source node to a destination node, and more particularly, to a method for performing packet flooding which enables efficient communication with a reduced requirement for network resources, by giving a first opportunity to a node at a predetermined distance to the source node to perform flooding of the packet from the source node.
2. Description of the Related Art
With the development of mobile communication devices and technologies, the demand for a small-scale wireless communication network other than an existing infrastructure network has risen. The small-scale wireless communication network is especially demanded in areas such as inside of a building or in a mountain, where wired equipment is difficult to install. A wireless ad hoc network is one example of a small-scale wireless communication network.
Unlike an infrastructure network, a wireless ad hoc network does not have a separate router for packet transmission and reception, and the respective nodes serve the role of either the host or the router. In a wireless ad hoc network, each node is equipped with a wireless communication device, and is movable. Accordingly, there is no fixed topology for a wireless ad hoc network.
In a wireless ad hoc network, due to limited transmission range of the wireless frequency of the respective nodes, packets from the source do not always reach the destination directly. In this case, the packets are transmitted to the destination via a plurality of nodes operating as a router. This is called ‘multihop’, and the wireless ad hoc network needs a routing protocol for the realization of a ‘multihop’ scheme.
Furthermore, because all the nodes share one data channel in the wireless ad hoc network, channel collision needs to be prevented, and to this end, many schemes have been suggested to prevent channel collision. One popular method among the channel collision schemes is the CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance), which is one of the MAC (media access control) layer protocols. The current Wireless LAN standard (described by IEEE 802.11) is one of its applications.
The CSMA/CA is the collision avoidance scheme based on the sensing of a carrier in the wireless net. According to the CSMA/CA, each node transmits a confirmation signal and starts transmitting the packets only after confirming that there would be no collision. This means that, if the plurality of nodes want to transmit packets in the network, the nodes have to transmit a plurality of confirmation signals to see if there would be no collision. Accordingly, the transmission is delayed.
According to the CSMA/CA, when a collision occurs in the network because more than one node concurrently attempt to transmit the packets using the data channel, the nodes delay packet transmission for a random period of time and attempt re-transmission later. Then upon detecting another collision, nodes delay the packet transmission two times as long as the previous delay time, and attempt re-transmission.
Accordingly, collisions more frequently occur in a complex network, delaying packet transmission of the nodes and subsequently delaying the overall transmission in the network. Power consumption of the network also increases. The collision at the MAC layer also impedes finding out the optimum route in the upper layer routing protocol.
Unlike the conventional wired network which is based on point-to-point communication, in the wireless ad hoc network, communication is carried out in the broadcasting/flooding way. That is, most of the wireless nodes transmit packets omnidirectionally to the neighboring wireless nodes, and all the neighboring nodes receiving the packets re-flood the packets. This type of flooding will be hereinafter called a ‘conventional flooding’.
FIG. 1 is a view for illustrating a collision and overlaying of flooding in the conventional ad hoc network. In FIG. 1, an exemplary wireless ad hoc network is constructed of a plurality of nodes 100, 110, 120, 130. The node 100 is a source node, and the other nodes 110, 120, 130 are neighboring nodes of the source node 100.
According to the conventional flooding, in order to ensure the widest packet receiving range possible, all the nodes first receiving the packet re-flood the received packets. As the neighboring nodes of the broadcasting node, which is the source node, try to use the shared channel to re-flood the received nodes at the same time, there occur frequent collisions.
Referring to FIG. 1, the neighboring nodes 110, 120, 130 are within the frequency transmission coverage 100′ of the source node 100, and accordingly receive the broadcast packets from the source node 100. If it is the first packet that they receive, all the neighboring nodes 110, 120, 130 attempt the re-flooding of the received packet using the shared channel almost simultaneously. However, none of the neighboring nodes 110, 120, 130 can perform re-flooding if there occurs a collision.
The network having nodes in higher density have more serious problems. That is, the greater the number of neighboring nodes of the source node, the more collisions that occur.
As shown in FIG. 1, the transmission coverage of the respective nodes overlay one another repeatedly. Accordingly, the same packet is re-flooded from the neighboring nodes of the source node unnecessarily many times, resulting in waste of network resources. In other words, as the same packets are re-flooded from the neighboring nodes 110, 120, 130 repeatedly in the coverage overlaying area of the respective nodes 110, 120, 130, the network resources are wasted.
Further, if collisions occur due to repetitive attempts of re-flooding, the respective neighboring nodes have to delay the packet transmission for a random period of time until the re-transmission. As a result, packet transmission is delayed, and power consumption of the respective nodes increases.